home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Add-Ons / MPW / MPW noweb 2.7 / examples / scanner.nw (.txt) < prev    next >
Encoding:
LaTeX Document  |  1995-05-30  |  14.9 KB  |  368 lines  |  [TEXT/MPS ]
  1. % Norman Ramsey (nr@notecnirp) --- CS 320
  2. \def\sizedboxit#1#2{\vtop{\vbox{\hrule\hbox{\vrule\kern #2%
  3.     \vtop{\vbox{\kern #2\hbox{#1}}\kern #2}\kern #2\vrule}}\hrule}}
  4. \def\boxit#1{\sizedboxit{#1}{1pt}}
  5. \def\token#1{\boxit{\strut\tt #1}}
  6. \setcounter{secnumdepth}{0}
  7. % l2h ignore boxit
  8. % l2h argblock token tt
  9. In this assignment I print intermediate code.
  10. <<grammatical C functions>>=
  11. void print6 (Exp e) {
  12.     extern int yylineno;
  13.     printf("line %d:\n",yylineno);
  14.     if (e.type==error_type)
  15.     printf("# ERROR\n");
  16.     else
  17.         printTree(e.tree,stdout);
  18. <<grammatical C declarations>>=
  19. void print6(Exp e);
  20. \section{The {\tt yacc} value stack}
  21. Here are all the objects I use as synthesized attributes:
  22. <<grammatical declarations>>=
  23. %union {
  24.     char *string;
  25.     Type type;
  26.     Product product;
  27.     Symbol symbol;
  28.     Exp exp;
  29.     Explist explist;
  30.     int bit;
  31. \section{3. Vocabulary and representation}
  32. \subsection{Representation of terminal symbols}
  33. {\tt yacc} and {\tt lex} use integers to represent terminal
  34. symbols (tokens).
  35. Single-character tokens are represented by their ASCII codes.
  36. Longer tokens are declared using {\tt yacc}'s [[%token]] declaration;
  37. {\tt yacc} chooses an integer representation of each such token.
  38. These representations are made available to the lexer via [[y.tab.h]].
  39. I use the standard trick from Kernighan and Pike ([[x.tab.h]] instead of 
  40. [[y.tab.h]]) to avoid remaking the lexer unecessarily.
  41. <<lexical include files>>=
  42. #include "x.tab.h"
  43. \subsection{1. Identifiers}
  44. Since {\tt lex} is notoriously slow at using patterns to recognize
  45.  reserved words, I look up every identifier in a table of reserved words.
  46. [[idcategory(id)]] returns the category of the reserved word [[id]]
  47. when [[id]] is in fact a reserved word.
  48. When [[id]] is not a reserved word, [[idcategory(id)]] returns [[IDENT]].
  49. <<lexical definitions>>=
  50. letter    [A-Za-z]
  51. digit    [0-9]
  52. The offensive [[<INITIAL>]] below has to do with handling comments (q.v.).
  53. Both identifiers and reserved words
  54. are saved in the string table and put on the {\tt yacc} value stack.
  55. <<lexical rules>>=
  56. <INITIAL>{letter}({letter}|{digit})*    { yylval.string = strsave(yytext);
  57.                       return idcategory(yytext); }
  58. <<lexical C declarations>>=
  59. extern char *strsave(char *s);
  60. <<grammatical declarations>>=
  61. %token IDENT
  62. %type <string> IDENT
  63. <<grammatical rules>>=
  64. ident    : IDENT
  65.         ;
  66. <<grammatical declarations>>=
  67. %type <string> ident
  68. <<grammatical C declarations>>=
  69. extern char yytext[];
  70. \subsection{2. Numbers}
  71. I have to use two different [[ScaleFactor]] definitions
  72. so I can tell the difference between long and short reals.
  73. Notice that the scale factor is {\em not} optional for the long real.
  74. <<lexical rules>>=
  75. <INITIAL>{digit}+|{digit}({hexDigit}*)[Hh]    { yylval.string = strsave(yytext); 
  76.                           return INTEGER; }
  77. <INITIAL>{digit}+"."{digit}*{EScaleFactor}?    { yylval.string = strsave(yytext); 
  78.                           return REAL; }
  79. <INITIAL>{digit}+"."{digit}*{DScaleFactor}    { yylval.string = strsave(yytext); 
  80.                           return LONGREAL; }
  81. <<grammatical declarations>>=
  82. %token <string> INTEGER REAL LONGREAL
  83. I permit lower case where Wirth insists on upper case.
  84. This will be convenient later on.
  85. Besides, Hanson does it.
  86. I need parentheses around things like [[EScaleFactor]] because I'n not
  87. really defining a regular expression---I'm using a macro facility.
  88. <<lexical definitions>>=
  89. hexDigit    [0-9A-Fa-f]
  90. EScaleFactor    ([eE][+\-]?{digit}+)
  91. DScaleFactor    ([dD][+\-]?{digit}+)
  92. \subsection{3,4. Strings and character constants}
  93. Single character strings [["x"]] become character constants,
  94. not strings, thanks to the {\tt lex} disambiguation rules.
  95. <<lexical rules>>=
  96. <INITIAL>"\'"{nonquote}"\'"        { yylval.string=strsave(yytext); return CHARCONST; }
  97. <INITIAL>{digit}{hexDigit}*[Xx]        { yylval.string=strsave(yytext); return CHARCONST; }
  98. <INITIAL>"\""{nondoublequote}*"\""  { yylval.string=strsave(yytext); return STRING; }
  99. <<grammatical declarations>>=
  100. %token <string> CHARCONST STRING
  101. The character set for string literals is awkward,
  102. because I want to include backslash escapes.
  103. I use the ANSI standard backslash escapes from section A2.5.2 of
  104. the second edition of Kernighan and Ritchie.
  105. Because the lexical analyzer is probably not the right place to
  106. handle illegal backslash escapes, I allow any reasonable
  107. character to follow the backslash.
  108. I define [[nonoctalx]] to be those characters
  109. that can't start an octal or hexadecimal constant (when following
  110. a backslash).
  111. Then I can recognize octal and hexdecimal character constants like [["\012"]].
  112. I {\em don't} insist that at least one [[hexDigit]] follow [[\x]],
  113. because again that should be handled downstream of the lexical analyzer.
  114. <<lexical definitions>>=
  115. plainnonquote         [ \t\]\"!#$%&()*+,\-./0-9:;<=>?@A-Z[^_`a-z{|}~]
  116. plainnondoublequote  [ \t\]\'!#$%&()*+,\-./0-9:;<=>?@A-Z[^_`a-z{|}~]
  117. escapedchar         (\\({nonoctalx}|{octal}{octal}?{octal}?|x{hexDigit}*))
  118. nonoctalx         [ \]\'\"!#$%&()*+,\-./89:;<=>?@A-Z[\\^_`a-wyz{|}~]
  119. nonquote         ({plainnonquote}|{escapedchar})
  120. nondoublequote         ({plainnondoublequote}|{escapedchar})
  121. octal             [0-7]
  122. I also need to handle strings that don't terminate.
  123. When I see one, I gobble up the whole line on which it sits---that should
  124. make it easier for the parser to recover.
  125. (The alternative is trying to tokenize the characters following the open
  126. quote.)
  127. <<lexical rules>>=
  128. <INITIAL>("\""{nondoublequote}*|"\'"{nonquote}*) <<complain; return bad string>>
  129. I print the first few characters of a nonterminated string,
  130. followed by an ellipsis.
  131. I return the string anyway because that way there's a chance that the parser
  132. can just ignore the error.
  133. <<complain; return bad string>>=
  134. {   yyerror("Unterminated string %.8s%s",yytext,yyleng>8?"...":"");
  135.     yylval.string=strsave("");
  136.     return STRING;
  137. I include prototypes for the string functions, to keep {\tt lcc -A}
  138. from complaining about missing prototypes.
  139. <<common include files>>=
  140. #include <string.h>
  141. \subsection{5. Operators and delimiters}
  142. Here are [[%token]] declarations for all the multicharacter tokens,
  143. including the reserved words.
  144. I use [[yyBEGIN]] because [[BEGIN]] means something special to {\tt lex}.
  145. <<grammatical declarations>>=
  146. %token ARROW INC DEC LSHIFT RSHIFT LEQ GEQ EQ NEQ AND OR 
  147.         /* -> ++ -- @<< @>> <= >= == != && || */
  148. I make sure the lexer always returns strings for identifiers
  149. and reserved words.
  150. Recognizing the operators and delimiters is straightforward:
  151. <<lexical rules>>=
  152. <INITIAL>"->"                           return ARROW;
  153. <INITIAL>"++"                           return INC;
  154. <INITIAL>"--"                           return DEC;
  155. <INITIAL>"<<"                           return LSHIFT;
  156. <INITIAL>">>"                           return RSHIFT;
  157. <INITIAL>"<="                           return LEQ;
  158. <INITIAL>">="                           return GEQ;
  159. <INITIAL>"=="                           return EQ;
  160. <INITIAL>"!="                           return NEQ;
  161. <INITIAL>"&&"                           return AND;
  162. <INITIAL>"||"                           return OR;
  163. <INITIAL>[\]+!\-*/~&.,;|()[{}^=#<>:]    return *yytext;
  164. \paragraph{Reserved word search}
  165. Recall that, instead of having the {\tt lex}-generated automaton
  166. recognize reserved words, I wanted to look up each identifier to see
  167. if it is a reserved word.
  168. I put the reserved words into an array and use binary search to find their
  169. categories.
  170. A word that isn't in the list has category [[IDENT]].
  171. The list itself is excruciating to read.
  172. I use a trick I got from Dave Hanson---I put the list in a header
  173. file as calls to the [[kw]] (keyword) macro.
  174. Then I include the header with appropriate macros wherever I need it.
  175. <<list of reserved words>>=
  176. kw(INT, "int")
  177. A binary search table of reserved words:
  178. <<reserved word data structures>>=
  179. static 
  180. struct reserved {char *s; int category;} 
  181. reservedwords[] = {
  182. #define kw(VAL,STRING) {STRING,VAL},
  183. <<list of reserved words>>
  184. #undef kw
  185. static int numreservedwords = (sizeof(reservedwords)/sizeof(struct reserved));
  186. [[idcategory]] is just binary search.
  187. <<lexical C functions>>=
  188. <<reserved word data structures>>
  189. static int idcategory (char *id) {
  190.     int low=0, high=numreservedwords-1, mid;
  191.     int compare;
  192.     while (low <= high) {
  193.     /* Invariant: if id is in the initial range low...high,
  194.               it is in the current range low...high */
  195.     mid = (low+high)/2;        /* note low <= mid <= high */
  196.     compare = strcmp(id,reservedwords[mid].s);
  197.     if (compare>0) low = mid + 1;
  198.     else if (compare<0) high = mid - 1;
  199.     else return reservedwords[mid].category;
  200.     }
  201.     return IDENT;        /* id is not a reserved word */
  202. <<lexical C declarations>>=
  203. static int idcategory(char *);
  204. \subsection{Comments}
  205. I use the standard trick of defining a special state just for comments.
  206. A begin comment sends the lexer into state [[<COMMENT>]], and an
  207. end comment returns it to state [[<INITIAL>]].
  208. All tokens that aren't comments are recognized only in state [[<INITIAL>]],
  209. which explains the offensive [[<INITIAL>]] prepended to every rule.
  210. <<lexical definitions>>=
  211. %S COMMENT
  212. <<lexical rules>>=
  213. <INITIAL>"/*"    BEGIN COMMENT;
  214. <COMMENT>"*/"    BEGIN INITIAL;
  215. <COMMENT>"\n"    ;
  216. <COMMENT>.    ;
  217. \subsection{Whitespace and bad characters}
  218. <<lexical rules>>=
  219. <INITIAL>[ \t\n]+        ; /* ignore whitespace */
  220. <INITIAL>.            <<complain about a bad character>>
  221. The error message we print is different for printable and nonprintable
  222. characters.
  223. <<complain about a bad character>>=
  224. {   if (*yytext >= ' ' && *yytext < 0177)
  225.          yyerror("bad character `%c'", *yytext);
  226.     else yyerror("bad character `\\%03o'", *yytext);
  227. \section{8. Expressions}
  228. \subsection{8.1 Operands (designators and constants)}
  229. There are no qualified identifiers, so this simplifies the parsing
  230. of designators.
  231. It is a bit awkward to distinguish variables and parameters from
  232. constant identifiers.
  233. There is also an awkwardness with rvalues---boolean expressions
  234. have to be converted from ``test'' to values using [[BOOL]].
  235. Following a suggestion of Hanson's, I use
  236. three nonterminals: [[exp]] is an expression (possibly a test);
  237. [[rvalue]] is an rvalue (never a test), and
  238. [[lvalue]] is an lvalue.
  239. I introduce [[complex_lvalue]] because I need to distinguish identifiers from
  240. all other lvalues (otherwise I get a reduce-reduce conflict when converting
  241. lvalues to expressions).
  242. <<grammatical declarations>>=
  243. %type <exp> arraydes lvalue complex_lvalue rvalue exp
  244. Here are productions for all the C literals.
  245. I use [[make_constval(type,string)]] to convert a string to a value of
  246. the type desired.
  247. I issue warnings for long reals, since they aren't supported in Oberon/320.
  248. <<grammatical rules>>=
  249. exp    : INTEGER      { $$ = make_constval(integer_type,$1); }
  250.           | REAL         { $$ = make_constval(real_type,$1); }
  251.           | LONGREAL     { warning("Long reals not supported (replaced with zero)");
  252.                  $$ = make_constval(real_type,strsave("0.0")); }
  253.          | CHARCONST    { $$ = make_constval(char_type,$1); }
  254.     | STRING    { $$ = make_constval(build_array(0,stringchar_type),$1); }
  255. \subsection{8.2 Operators}
  256. I use {\tt yacc} precedence declarations.
  257. These declarations define precedence.
  258. My task is much simplified because unary and binary [[-]] have
  259. exactly the same precedence.
  260. <<grammatical declarations>>=
  261. %left OR
  262. %left AND
  263. %left '|'
  264. %left '^'
  265. %left '&'
  266. %left EQ NEQ
  267. %left '<' '>' LEQ GEQ
  268. %left LSHIFT RSHIFT
  269. %left '+' '-' 
  270. %left '*' '/' '%'
  271. %right '!' '~' INC DEC                 /* unary operators */
  272. %left ARROW '.'
  273. [[binop]] checks types and generates intermediate code.
  274. Consult the chapter on typechecking for the description of the
  275. correct operation of [[binop]] and the meanings of
  276. various permissions [[p_xxx]].
  277. <<grammatical rules>>=
  278. complex_lvalue    : lvalue '.' ident        { $$ = find_field($1,$3); }
  279.         | exp ARROW ident         { $$ = find_field(deref($1),$3) }
  280.         | '*' rvalue            { $$ = deref($1); }
  281.         | arraydes ']'            { $$ = $1; }
  282. arraydes    : rvalue '[' exp         { $$ = subscript($1,$3); }
  283. lvalue         : complex_lvalue        { $$ = $1; }
  284.         | ident                { $$ = lookup_lvalue($1); }
  285. exp        : complex_lvalue        { $$.type=$1.type; 
  286.                           $$.tree=tMEM($1.type->size,$1.tree); }
  287.         | ident                { $$ = lookup_exp($1); }
  288. rvalue        : exp                { $$ = boolval($1); }
  289. <<grammatical rules>>=
  290. exp        : exp EQ exp     { $$ = binop(OSeq, $1,$3,boolean_type,p_equality); }
  291.         | exp NEQ exp      { $$ = binop(OSneq,$1,$3,boolean_type,p_equality); }
  292.         | exp '<' exp      { $$ = binop(OSlt, $1,$3,boolean_type,p_relational); }
  293.         | exp LEQ exp      { $$ = binop(OSleq,$1,$3,boolean_type,p_relational); }
  294.         | exp '>' exp      { $$ = binop(OSgt, $1,$3,boolean_type,p_relational); }
  295.         | exp GEQ exp      { $$ = binop(OSgeq,$1,$3,boolean_type,p_relational); }
  296. exp        : exp '+' exp     { $$ = binop(OSplus, $1,$3,0,p_numeric); }
  297.         | exp '-' exp     { $$ = binop(OSminus,$1,$3,0,p_numeric); }
  298.         | exp OR exp      { $$ = binop(OSor,   $1,$3,0,p_boolean); }
  299. exp        : exp '*' exp     { $$ = binop(OSmul,  $1,$3,0,p_numeric); }
  300.         | exp AND exp    { $$ = binop(OSand,$1,$3,0,p_boolean); }
  301. exp        : '(' exp ')'    { $$ = $2; }
  302. \subsection{Function calls}
  303. Calls to functions (procedures having a return type)
  304. may occur {\em only} as factors in the production given below.
  305. bottom of p.~678 of the Oberon report makes it clear that the~[[()]] are
  306. required even if the function has no parameters.
  307. <<not yet grammatical rules>>=
  308. exp        : ident ActualParameters     { $$ = fcall($1,$2); }
  309. ActualParameters: '(' ExpList ')'        { $$ = $2; }
  310.         | '(' ')'            { $$ = 0; }
  311. ExpList        : rvalue ',' ExpList        { $$ = explist($1,$3); }
  312.         | rvalue            { $$ = explist($1,0); }
  313. <<not yet grammatical declarations>>=
  314. %type <explist> ActualParameters ExpList
  315. \section{11. Compilation units}
  316. <<grammatical rules>>=
  317. module    : exp                    { compile($1); }
  318. <<grammatical declarations>>=
  319. %start module
  320. \section{Error recovery}
  321. Here are some simple error productions that might help the parser continue.
  322. The first four gobble up mangled declarations.
  323. The last two are stabs in the dark; I hope they give the parser a chance
  324. to recover from errors in statements and expressions.
  325. <<grammatical rules>>=
  326. exp        : error            { $$.type = error_type; }
  327. \section{Putting it all together}
  328. Here are the necessary {\tt\#include} files:
  329. <<common include files>>=
  330. #include <assert.h>
  331. #include <stdio.h>
  332. #include "types.h"
  333. #include "predef.h"
  334. #include "tree.h"
  335. #include "typecheck.h"
  336. #include "codegen.h"
  337. #include "symbol.h"
  338. #include "declarations.h"
  339. #include "constants.h"
  340. #include "errors.h"
  341. There are no include files used exclusively by the parser.
  342. This is because the lexer sees {\tt y.tab.h}, and so has to know everything
  343. the parser knows.
  344. <<grammatical include files>>=
  345. This is boilerplate for every {\tt lex} specification ever written:
  346. <<lexer>>=
  347. <<common include files>>
  348. <<lexical include files>>
  349. <<lexical C declarations>>
  350. <<lexical definitions>>
  351. <<lexical rules>>
  352. <<lexical C functions>>
  353. And this is boilerplate for every {\tt yacc} specification ever written:
  354. <<parser>>=
  355. <<common include files>>
  356. <<grammatical include files>>
  357. <<grammatical C declarations>>
  358. extern int yylex(void);
  359. <<grammatical declarations>>
  360. <<grammatical rules>>
  361. #define lint  /* keep lcc from barking about no reference to yaccpar_sccsid */
  362. <<grammatical C functions>>
  363. \section{Indices}
  364. \subsection{Chunks}
  365. \nowebchunks
  366. \subsection{Identifiers}
  367. \nowebindex
  368.